package 热题100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/*
思路：
1，三指针，对数组进行排序
2，定位一个位置i指针，为标志位，l指针每次从i+1开始，r每次最后开始
3，如果三个数字之和大于target，r--；否则l++；
4，如果找到满足条件的，将i，l，三个数添加到结果集中
5，每次循环的终止条件：l >= r;
6，所有循环的终止条件：i == arr.length - 2;
 */


public class 热题15三数之和 {


    public static void main(String[] args) {
        int[] arr = {-1,0,1,2,-1,-4};
        热题15三数之和 o = new 热题15三数之和();
        List<List<Integer>> lists = o.threeSum(arr);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }

    /**
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3 || nums == null){
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> resList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 &&  nums[i] == nums[i-1]) continue;
            int l = i + 1;
            int r = nums.length-1;
            while (l < r){
                int sum = nums[i] + nums[l] + nums[r];
                if (sum < 0){
                    l++;
                }else if (sum > 0){
                    r--;
                }else {
                    //直接将这三个数作为链表
                    resList.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //如果l 《 r ，相邻l和r相等，当前的l和r的结果已经计算，在计算就是重复的值，所以直接跳过
                    while (l < r && nums[l] == nums[++l]);
                    while (l < r && nums[r] == nums[--r]);
                }
            }
        }
        return resList;
    }
}
